// samsung.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "line.h"
#include "direction.h"

#include <string>
#include <vector>
#include <iostream>
#include <stdlib.h>
#include <map>

std::vector<Samsung::Point> setOfPoints;

std::string GenerateTestCase(int len)
{
	std::string result(len, 'r');
	std::string result1(len + 4, 'l');
	result.append(result1);
	for (int i = 0; i < len + len + 4; ++i)
	{
		int fst = rand() % (len + len + 4);
		int scnd = rand() % (len + len + 4);
		char tmp = result[fst];
		result[fst] = result[scnd];
		result[scnd] = tmp;
	}
	return result;
}

bool ChechDoesHitAPoint(const std::vector<Samsung::Point>& points, const Samsung::Point& p, int count)
{
	for (int i = 0; i < count; ++i)
	{
		Samsung::Line l(points[i], points[i + 1]);
		if (l.IsIncludePoint(p))
			return true;
	}
	return false;
}

struct SamsungNode {
	std::map<Samsung::Point, SamsungNode * > inheritors;
	SamsungNode( ) {
	}
};

class SamsungTree {
public:
	SamsungTree() {}
	~SamsungTree() {}
	bool CheckPath(const std::vector<Samsung::Point> & inheritors);
	void AddPath(const std::vector<Samsung::Point> & inheritors);
private:
	bool CheckPathHelper(const std::vector<Samsung::Point> & inheritors, SamsungNode & node, int index) {
		// 
		if (index >= inheritors.size()) {
			return false;
		}//if IS the point
		if (node.inheritors.find(inheritors[index]) != node.inheritors.end()) {
			return CheckPathHelper(inheritors, *node.inheritors[inheritors[index]], index + 1);
		}
		return true;
	}
	SamsungNode * FindLongestMatch(const std::vector<Samsung::Point> & inheritors, SamsungNode & node, int & index) {
		if ( index + 1 == inheritors.size() ) {
			return &node;
		}
		if (node.inheritors.find(inheritors[index + 1]) == node.inheritors.end()) {
			return &node;
		}
		return FindLongestMatch(inheritors, *node.inheritors[inheritors[index + 1]], index);
	}

	SamsungNode _node;
};

SamsungTree pathes;

bool SamsungTree::CheckPath(const std::vector<Samsung::Point> & inheritors) {
	return CheckPathHelper(inheritors, _node, 0);
}

void SamsungTree::AddPath(const std::vector<Samsung::Point> & inheritors) {
	int index = 0;

	SamsungNode * node = FindLongestMatch(inheritors, _node, index);

	for (int i = index; i < inheritors.size(); i++) {
		node->inheritors[inheritors[i]] = new SamsungNode();
		node = node->inheritors[inheritors[i]];
	}
}

bool GetNextIntersects(std::vector<Samsung::Point>& points,
	std::vector<Samsung::Direction>& directions,
	const std::string& letters,
	int index,
	int& dist)
{
	if (index + 1 >= letters.length())
	{
		if (points.front().first_ != points.back().first_)
		{
			dist = points.back().first_ - points.front().first_;
			return false;
		}
		if (points.back().second_ > 10000)
			return  true;

		std::vector<Samsung::Point> fake_points(points.begin() + 1, points.end());
		return !ChechDoesHitAPoint(fake_points, points[0], fake_points.size() - 1); 
	}

	directions.resize(index + 1);
	points.resize(index + 1);
	pathes.AddPath(points);

	char letter = letters[index];
	Samsung::Direction direction = Samsung::GetNextDirection(directions[index], letter);
	directions.push_back(direction);

	Samsung::Point deltha = Samsung::GetDeltha(direction);
	if (ChechDoesHitAPoint(points, points[index] + deltha, index))
		return false;

	points.push_back(points[index] + deltha);
	
	while (!GetNextIntersects(points, directions, letters, index + 1, dist))
	{
		if (dist < 0)
		{
			if (points[index + 1].first_ - points[index].first_ < -1)
			{
				dist -= (points[index + 1].first_ - points[index].first_ + 1);
				if (dist <= 0)
				{
					dist = 0;
					return false;
				}
			}

			if (points[index + 1].first_ - points[index].first_ > 0)
			{
				points[index + 1].first_ -= dist;
				if (!pathes.CheckPath(std::vector<Samsung::Point>(points.begin(), points.begin() + index + 2))) {
					points[index + 1].first_ += dist;
					dist = 0;
					return false;
				}
				dist = 0;
				continue;
			}
		}

		if (dist > 0)
		{
			if (points[index + 1].first_ - points[index].first_ > 1)
			{
				dist -= (points[index + 1].first_ - points[index].first_ - 1);
				if (dist <= 0)
				{
					dist = 0;
					return false;
				}
			}
			if (points[index + 1].first_ - points[index].first_ < 0)
			{
				points[index + 1].first_ -= dist;
				if ( !pathes.CheckPath(std::vector<Samsung::Point>(points.begin(), points.begin() + index + 2))) {
					points[index + 1].first_ += dist;
					dist = 0;
					return false;
				}
				dist = 0;
				continue;
			}
			return false;
		}

		if (index + 1 == letters.length())
			return false;

		if (dist != 0)
			return false;

		
		points[index + 1] = points[index + 1] + deltha;
		if (ChechDoesHitAPoint(points, points[index + 1], index))
			return false;
		if (!pathes.CheckPath(std::vector<Samsung::Point>(points.begin(), points.begin() + index + 2))) {
			points[index + 1] = points[index + 1] - deltha;
			return false;
		}
	}
	return true;
}

int CalculateArea(const std::vector<Samsung::Point>& points)
{
	int result = 0;
	for (int i = 0; i < points.size() - 1; ++i)
	{
		result += (points[i].first_ - points[i + 1].first_) * (points[i + 1].second_ + points[i].second_) / 2;
	}
	return result;
}

void NormilizePoints(std::vector<Samsung::Point>& points)
{
	Samsung::Point deltha;
	for (int i = 0; i < points.size(); ++i)
	{
		if (points[i].first_ < deltha.first_)
			deltha.first_ = points[i].first_;
		if (points[i].second_ < deltha.second_)
			deltha.second_ = points[i].second_;
	}

	for (int i = 0; i < points.size(); ++i)
	{
		points[i] = points[i] - deltha;
	}
}

void ProceedCase(const std::string& letters, int caseNumber)
{
	std::cout << "Case# " << caseNumber << '\n';

	std::vector<Samsung::Point> points;
	points.push_back(Samsung::Point(0, 0));

	std::vector<Samsung::Direction> directions;
	directions.push_back(Samsung::UP);

	int dist = 0;

	bool result = GetNextIntersects(points, directions, letters, 0, dist);
	NormilizePoints(points);
	int area = CalculateArea(points);
	std::cout << area << "\n";

	for (int i = 0; i < points.size(); ++i)
		std::cout << points[i].first_ << " " << points[i].second_ << " ";
	std::cout << "\n";
}

int main()
{
	int i = 0;
	const int maxSymbols = 1024;
	char string[maxSymbols];
	std::vector<std::string> params;
	
	
	//std::cout << true << std::endl;
	/*	while (std::cin.getline(string, maxSymbols))
	params.push_back(std::string(string));

	for (int i = 0; i < params.size(); ++i)
	{
	ProceedCase(params[i], i + 1);
	}
	*/
//	ProceedCase("LLLL", i + 1);
	ProceedCase("LLLRLRLRLLLRLRL", 2);
	return 0;
}